package q433_minMutation;

import java.util.*;

public class Solution {
    public int minMutation(String start, String end, String[] bank) {
        if (start.equals(end)) {
            return 0;
        }
        Set<String> visited = new HashSet<>();
        char[] keys = {'A', 'C', 'G', 'T'};
        // 将基因库中的所有元素先加入cnt中
        Set<String> cnt = new HashSet<>(Arrays.asList(bank));
        // 如果没有end对应的元素 则直接返回-1
        if (!cnt.contains(end)) {
            return -1;
        }
        // 使用BFS来对变化进行检索
        Queue<String> queue = new ArrayDeque<String>();
        // 首先压入start
        queue.offer(start);
        // visited用来保存哪些基因组合已经出现过
        visited.add(start);
        // 记录变化步数
        int step = 1;
        while (!queue.isEmpty()) {
            // 对于BFS 每次都需要记录queue的size来运算
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                // 依次取出queue中元素
                String curr = queue.poll();
                // 接下来两个循环也就是按照每个基因序列具有八个字符
                // 并且每个字符变化最多有三个 按照遍历的形式对基因序列进行修改
                for (int j = 0; j < 8; j++) {
                    for (int k = 0; k < 4; k++) {
                        if (keys[k] != curr.charAt(j)) {

                            StringBuilder sb = new StringBuilder(curr);
                            // 改变j位置的字符
                            sb.setCharAt(j, keys[k]);
                            // 得到变化后的基因序列
                            String next = sb.toString();
                            if (!visited.contains(next) && cnt.contains(next)) {
                                if (next.equals(end)) {
                                    return step;
                                }
                                // 注意 在将next压入栈中的同时
                                // 还需要将next加入visited 通过visited避免反复修改出现同一个序列
                                queue.offer(next);
                                visited.add(next);
                            }
                        }
                    }
                }
            }
            step++;
        }
        return -1;


    }
}
